{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest String Chain"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #two-pointers #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #双指针 #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestStrChain"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最长字符串链"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给出一个单词数组&nbsp;<code>words</code>&nbsp;，其中每个单词都由小写英文字母组成。</p>\n",
    "\n",
    "<p>如果我们可以&nbsp;<strong>不改变其他字符的顺序&nbsp;</strong>，在 <code>word<sub>A</sub></code>&nbsp;的任何地方添加 <strong>恰好一个</strong> 字母使其变成&nbsp;<code>word<sub>B</sub></code>&nbsp;，那么我们认为&nbsp;<code>word<sub>A</sub></code>&nbsp;是&nbsp;<code>word<sub>B</sub></code>&nbsp;的 <strong>前身</strong> 。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<code>\"abc\"</code>&nbsp;是&nbsp;<code>\"abac\"</code>&nbsp;的 <strong>前身</strong>&nbsp;，而&nbsp;<code>\"cba\"</code>&nbsp;不是&nbsp;<code>\"bcad\"</code>&nbsp;的 <strong>前身</strong></li>\n",
    "</ul>\n",
    "\n",
    "<p><strong>词链</strong>是单词&nbsp;<code>[word_1, word_2, ..., word_k]</code>&nbsp;组成的序列，<code>k &gt;= 1</code>，其中&nbsp;<code>word<sub>1</sub></code>&nbsp;是&nbsp;<code>word<sub>2</sub></code>&nbsp;的前身，<code>word<sub>2</sub></code>&nbsp;是&nbsp;<code>word<sub>3</sub></code>&nbsp;的前身，依此类推。一个单词通常是 <code>k == 1</code> 的 <strong>单词链</strong>&nbsp;。</p>\n",
    "\n",
    "<p>从给定单词列表 <code>words</code> 中选择单词组成词链，返回 词链的&nbsp;<strong>最长可能长度</strong> 。<br />\n",
    "&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>words = [\"a\",\"b\",\"ba\",\"bca\",\"bda\",\"bdca\"]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>最长单词链之一为 [\"a\",\"<u>b</u>a\",\"b<u>d</u>a\",\"bd<u>c</u>a\"]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>words = [\"xbc\",\"pcxbcf\",\"xb\",\"cxbc\",\"pcxbc\"]\n",
    "<b>输出：</b>5\n",
    "<b>解释：</b>所有的单词都可以放入单词链 [\"xb\", \"xb<u>c</u>\", \"<u>c</u>xbc\", \"<u>p</u>cxbc\", \"pcxbc<u>f</u>\"].\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>words = [\"abcd\",\"dbqca\"]\n",
    "<strong>输出：</strong>1\n",
    "<b>解释：</b>字链[\"abcd\"]是最长的字链之一。\n",
    "[\"abcd\"，\"dbqca\"]不是一个有效的单词链，因为字母的顺序被改变了。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= words.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= words[i].length &lt;= 16</code></li>\n",
    "\t<li><code>words[i]</code>&nbsp;仅由小写英文字母组成。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-string-chain](https://leetcode.cn/problems/longest-string-chain/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-string-chain](https://leetcode.cn/problems/longest-string-chain/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"a\",\"b\",\"ba\",\"bca\",\"bda\",\"bdca\"]', '[\"xbc\",\"pcxbcf\",\"xb\",\"cxbc\",\"pcxbc\"]', '[\"abcd\",\"dbqca\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ord_sum(self, word):\n",
    "        res = 0\n",
    "        for w in word:\n",
    "            res += ord(w)\n",
    "        return res\n",
    "    \n",
    "    def longestStrChain(self, words: List[str]) -> int:\n",
    "        # you got on the right direction, but do not finish it ....\n",
    "        # res = 1\n",
    "        # c_dict = collections.defaultdict(list)\n",
    "        # seen = collections.defaultdict(int)\n",
    "        # for word in words:\n",
    "        #     c_dict[len(word)].append(word)\n",
    "        # for c in c_dict[1]:\n",
    "        #     seen[c] = 1\n",
    "        # for c in sorted(c_dict.keys()):\n",
    "        #     if c - 1 in c_dict:\n",
    "        #         before = len(seen)\n",
    "        #         for word in c_dict[c]:\n",
    "        #             for w in c_dict[c-1]:\n",
    "        #                 if w in seen and self.ord_sum(word) - self.ord_sum(w) in range(97, 123):\n",
    "        #                     seen[word] = seen[w] + 1\n",
    "        #             if word in seen:\n",
    "        #                 res = max(res, seen[word])\n",
    "        # return res\n",
    "    \n",
    "        dp = collections.defaultdict(lambda: 1)\n",
    "        size_map = collections.defaultdict(set)\n",
    "        for word in words:\n",
    "            size_map[len(word)].add(word)\n",
    "        ans = 1\n",
    "        keys = sorted(size_map.keys())\n",
    "        for lg in keys:\n",
    "            if lg == 1:\n",
    "                continue\n",
    "            same_size_word = size_map[lg]\n",
    "            if lg-1 not in size_map: continue\n",
    "            smaller_words = size_map[lg-1]\n",
    "            for word in same_size_word:\n",
    "                val = 1\n",
    "                for i in range(lg):\n",
    "                    test_word = word[:i]+word[i+1:]\n",
    "                    if test_word in smaller_words:\n",
    "                        val = max(dp[test_word]+1, val)\n",
    "                dp[word] = val\n",
    "                ans = max(ans, val)\n",
    "        return ans\n",
    "                \n",
    "                \n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestStrChain(self, words: list) -> int:\n",
    "        words.sort(key=lambda x:len(x))\n",
    "        words = [''] + words\n",
    "        dp = [1 for i in range(len(words))]\n",
    "        dp[0] = 0\n",
    "        ans = 1\n",
    "        for i in range(1,len(words)):\n",
    "            for j in range(i-1,-1,-1):\n",
    "                if len(words[j]) + 1 < len(words[i]):\n",
    "                    break\n",
    "                if len(words[j]) + 1 != len(words[i]):\n",
    "                    continue\n",
    "                cnt = 0\n",
    "                for k in words[i]:\n",
    "                    if cnt < len(words[j]) and k == words[j][cnt]:\n",
    "                        cnt += 1\n",
    "                if cnt == len(words[j]):\n",
    "                    dp[i] = max(dp[i],dp[j]+1)\n",
    "                    ans = max(ans,dp[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestStrChain(self, words: List[str]) -> int:\n",
    "        sorted_words = sorted(words, key=len)\n",
    "        arr = [0] * 17\n",
    "        for i,w in enumerate(sorted_words):\n",
    "            arr[len(w)] = i\n",
    "        dp = [1] * len(sorted_words)\n",
    "        for i,w in enumerate(sorted_words):\n",
    "            for j in range(arr[len(w)-1]+1):\n",
    "                if self.isSub(sorted_words[j], sorted_words[i]):\n",
    "                    dp[i] = max(dp[j]+1, dp[i])\n",
    "        return max(dp)\n",
    "\n",
    "    def isSub(self, a, b):\n",
    "        if len(a)+1 != len(b):\n",
    "            return False\n",
    "        i = 0\n",
    "        for j in range(len(b)):\n",
    "            if i < len(a) and a[i] == b[j]:\n",
    "                i += 1\n",
    "        return i == len(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestStrChain(self, words: List[str]) -> int:\n",
    "        words.sort(key=lambda w: len(w))\n",
    "        dp = {}\n",
    "        for word2 in words:\n",
    "            longest = 0\n",
    "            for j in range(len(word2)):\n",
    "                word1 = word2[:j] + word2[j + 1:]\n",
    "                longest = max(longest, dp.get(word1, 0) + 1)\n",
    "            dp[word2] = longest\n",
    "        return max(dp.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestStrChain(self, words: List[str]) -> int:\n",
    "        #DP\n",
    "        #dp[i]，以nums[i]结尾mxl\n",
    "        #dp[i] = max(dp[j]+1) if exp(nums[j],nums[i])==True, 0<=j<i\n",
    "        #li = sorted(words,key=len(o))\n",
    "        def exp(a,b):\n",
    "            if len(a)-len(b)!=1:return False \n",
    "            i, j = 0, 0\n",
    "            count = 0\n",
    "            while i<len(a) and j<len(b):\n",
    "                if a[i]==b[j]:\n",
    "                    i+=1\n",
    "                    j+=1\n",
    "                else:\n",
    "                    count+=1 \n",
    "                    i+=1\n",
    "            return count<=1\n",
    "        n = len(words)\n",
    "        words = sorted(words,key = len)\n",
    "        print(words)\n",
    "        dp = n*[1]\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "               if exp(words[i],words[j]):\n",
    "                   dp[i] = dp[j] + 1 \n",
    "        print(dp)\n",
    "        return max(dp)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestStrChain(self, words: List[str]) -> int:\n",
    "        d1 = {}\n",
    "        kk, kk1 = 0, 0\n",
    "        for i in words:\n",
    "            kk = max(kk,len(i))\n",
    "            try:\n",
    "                d1[len(i)].append(i)\n",
    "                kk1 = max(kk1,len(d1[len(i)]))\n",
    "            except:\n",
    "                d1[len(i)] = [i]\n",
    "        d = [1]*(kk1+1)\n",
    "        d2 = [1]*(kk1+1)\n",
    "        ans = 1\n",
    "        #print(kk1)\n",
    "        for k in range(2,kk+1):\n",
    "            try:\n",
    "                a,b=d1[k],d1[k-1]\n",
    "                for i in range(len(a)):\n",
    "                    for j in range(len(b)):\n",
    "                        m,n=0,0\n",
    "                        c =0\n",
    "                        while n<k-1:\n",
    "                            if a[i][m]!=b[j][n]:\n",
    "                                m +=1\n",
    "                                c +=1\n",
    "                            else:\n",
    "                                m+=1\n",
    "                                n+=1\n",
    "                            if c == 2:\n",
    "                                break\n",
    "                        if c != 2:\n",
    "                            d2[i] = max(d2[i],d[j]+1)\n",
    "                d,d2 = d2,[1]*(kk1+1)\n",
    "                ans = max(ans,max(d))\n",
    "                #print(d)\n",
    "            except:\n",
    "                pass\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestStrChain(self, words: List[str]) -> int:\n",
    "        n=len(words)\n",
    "        dic={w:1 for w in words}\n",
    "        words2=[w for w in words if len(w)>1]\n",
    "        words2.sort(key=len)\n",
    "        res=1\n",
    "        for w in words2:\n",
    "            for i in range(len(w)):\n",
    "                nw=w[:i]+w[i+1:]\n",
    "                dic[w]=max(dic[w],dic.get(nw,0)+1)\n",
    "            res=max(res,dic[w])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestStrChain(self, words: List[str]) -> int:\n",
    "        # dp[k] = max(dp[k - 1], foreach(0 - (k - 1)) lianjie ok +1)\n",
    "        words.sort(key=lambda x: len(x))\n",
    "        print(words)\n",
    "        dp = [1] * len(words)\n",
    "        for i in range(1, len(words)):\n",
    "            for j in range(0, i):\n",
    "                t = 0\n",
    "                if self.isValid(words[j], words[i]):\n",
    "                    t = dp[j] + 1\n",
    "                dp[i] = max(dp[i], t)\n",
    "\n",
    "        print(dp)\n",
    "        return max(dp)\n",
    "\n",
    "\n",
    "    def isValid(self, pre:str, cur:str) -> bool:\n",
    "        if len(pre) + 1 != len(cur):\n",
    "            return False\n",
    "        index_pre = 0\n",
    "        index_cur = 0\n",
    "        while index_pre < len(pre) and index_cur < len(cur):\n",
    "            while index_cur < len(cur) and cur[index_cur] != pre[index_pre]:\n",
    "                index_cur += 1\n",
    "            if index_cur >= len(cur):\n",
    "                break\n",
    "            index_pre += 1\n",
    "            index_cur += 1\n",
    "        if pre == 'ca' and cur == 'dca':\n",
    "            print(index_pre)\n",
    "            print(index_cur)\n",
    "            print(index_pre >= len(pre))\n",
    "\n",
    "        if index_pre >= len(pre):\n",
    "            return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestStrChain(self, words: List[str]) -> int:\n",
    "        # 加一个字母\n",
    "        res = 1\n",
    "        record = [[] for _ in range(16)]\n",
    "        words.sort(key = lambda x: len(x))\n",
    "        for word in words:\n",
    "            length = len(word)\n",
    "            link_num = 1\n",
    "            if length==1:\n",
    "                record[0].append((word, link_num))\n",
    "            elif not record[length-2]:\n",
    "                record[length-1].append((word, link_num))\n",
    "            else:\n",
    "                for candi_word, candi_link in record[length-2]:\n",
    "                    if self.predes(candi_word, word, length-1, length):\n",
    "                        link_num = max(link_num, candi_link+1)\n",
    "                record[length-1].append((word, link_num))\n",
    "                res = max(res, link_num)\n",
    "        print(record)\n",
    "        return res\n",
    "    \n",
    "    def predes(self, word1, word2, m, n):\n",
    "        i, j=0,0\n",
    "        while i<m and j<n:\n",
    "            if word1[i]==word2[j]:\n",
    "                i+= 1\n",
    "                j += 1\n",
    "            else:\n",
    "                j += 1\n",
    "        if i!= m:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def judge(self, s1, s2):\n",
    "        if len(s2) != len(s1) + 1:\n",
    "            return 0 \n",
    "        i = 0\n",
    "        for item in s2:\n",
    "            if item == s1[i]:\n",
    "                i += 1 \n",
    "            if i == len(s1):\n",
    "                return 1 \n",
    "        return 0 \n",
    "\n",
    "    def longestStrChain(self, words: List[str]) -> int:\n",
    "        to = {}\n",
    "        for i in range(len(words)):\n",
    "            to[i] = []\n",
    "            for j in range(len(words)):\n",
    "                if self.judge(words[i], words[j]):\n",
    "                    to[i].append(j)\n",
    "                     \n",
    "        dp = [0] * len(words)\n",
    "        def dfs(i):\n",
    "            if dp[i] != 0: return dp[i]\n",
    "            dp[i] = 1\n",
    "            for nxt in to[i]:\n",
    "                dp[i] = max(dp[i], dfs(nxt)+1)\n",
    "            return dp[i]\n",
    "        for i in range(len(words)):\n",
    "           dfs(i)\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestStrChain(self, words: List[str]) -> int:\n",
    "        n = len(words)\n",
    "        words.sort(key = lambda x: -len(x))\n",
    "        mp = defaultdict(lambda: 1)\n",
    "        ans = 1\n",
    "\n",
    "        for word in words:\n",
    "            for i in range(len(word)):\n",
    "                new = word[:i] + word[i+1:]\n",
    "                if new in words:\n",
    "                    mp[new] = mp[word] + 1\n",
    "                    ans = max(ans, mp[new])\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestStrChain(self, words: List[str]) -> int:\n",
    "        n=len(words)\n",
    "        dp=[1]*n\n",
    "        def isSeq(word1,word2):\n",
    "            # 判断word1是不是word2的前身\n",
    "            n1=len(word1)\n",
    "            n2=len(word2)\n",
    "            if n2-n1==1:\n",
    "                j=0\n",
    "                i=0\n",
    "                while i<n1 and j<n2:\n",
    "                    if word1[i]==word2[j]:\n",
    "                        i+=1\n",
    "                        j+=1\n",
    "                    else:\n",
    "                        j+=1\n",
    "                if i<n1:\n",
    "                    return False\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        words.sort(key=lambda x:len(x))\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if isSeq(words[i],words[j]):\n",
    "                    dp[j]=max(dp[j],dp[i]+1)\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestStrChain(self, words: List[str]) -> int:\n",
    "        cnt = defaultdict(int)\n",
    "        words.sort(key=len)\n",
    "        res = 0\n",
    "        for word in words:\n",
    "            cnt[word] = 1\n",
    "            for i in range(len(word)):\n",
    "                prev = word[:i] + word[i+1:]\n",
    "                if prev in cnt:\n",
    "                    cnt[word] = max(cnt[word], cnt[prev] + 1)\n",
    "            res = max(res, cnt[word])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestStrChain(self, words: List[str]) -> int:\n",
    "        words.sort(key = lambda x : len(x))\n",
    "        dp = collections.Counter()\n",
    "        res = 0\n",
    "        for i, w in enumerate(words):\n",
    "            for j in range(len(w)):\n",
    "                cur = w[:j] + w[j+1:]\n",
    "                dp[w] = max(dp[cur] + 1, dp[w])\n",
    "            res = max(res, dp[w])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def longestStrChain(self, words: List[str]) -> int:\n",
    "        n = len(words)\n",
    "\n",
    "        g = {}\n",
    "        rank_by_word = { words[i] : i for i in range(n) }\n",
    "        is_in_by_rank = {}\n",
    "\n",
    "        for i in range(n):\n",
    "            w = words[i]\n",
    "\n",
    "            for j in range(len(w)):\n",
    "                prefix = w[:j]\n",
    "                suffix = w[j + 1:]\n",
    "                pw = prefix + suffix\n",
    "\n",
    "                if rank_by_word.get(pw) != None:\n",
    "                    p = rank_by_word[pw]\n",
    "                    neighbors = g.get(p, {})\n",
    "                    neighbors[i] = True\n",
    "                    g[p] = neighbors\n",
    "                    is_in_by_rank[i] = True\n",
    "        \n",
    "        # BFS \n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            if not is_in_by_rank.get(i):\n",
    "                q.append((i, 1))\n",
    "        \n",
    "        max_len = 1\n",
    "        checked = {}\n",
    "        while q:\n",
    "            node, chain_len = q.popleft()\n",
    " \n",
    "            if chain_len > max_len:\n",
    "                max_len = chain_len\n",
    "\n",
    "            neighbors = g.get(node, {})\n",
    "            for neighbor in neighbors:\n",
    "                if checked.get(neighbor, -1) >= chain_len + 1:\n",
    "                    continue\n",
    "                \n",
    "                checked[neighbor] = chain_len + 1\n",
    "                q.append((neighbor, chain_len + 1))\n",
    "        \n",
    "        return max_len\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestStrChain(self, words: List[str]) -> int:\n",
    "        nums=[ len(w) for w in words]\n",
    "        t=zip(words,nums)\n",
    "        t=sorted(t,key=lambda x:(x[1],x[0]),reverse=False)\n",
    "        words,nums=zip(*t)\n",
    "        words=list(words)\n",
    "        print(words)\n",
    "        \n",
    "        n=len(words)\n",
    "        cnt=defaultdict(int)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            word=words[i]\n",
    "            cnt[word]=1\n",
    "            for j in range(len(word)):\n",
    "                prev=word[:j]+word[j+1:]\n",
    "                if prev in cnt:\n",
    "                    cnt[word]=max(cnt[word],cnt[prev]+1)\n",
    "                ans=max(ans,cnt[word])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestStrChain(self, words: List[str]) -> int:\n",
    "        cnt = defaultdict(int)\n",
    "        words.sort(key=len)\n",
    "        res = 0\n",
    "        for word in words:\n",
    "            cnt[word] = 1\n",
    "            for i in range(len(word)):\n",
    "                prev = word[:i] + word[i+1:]\n",
    "                if prev in cnt:\n",
    "                    cnt[word] = max(cnt[word], cnt[prev] + 1)\n",
    "            if cnt[word] > res:\n",
    "                res = cnt[word]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestStrChain(self, words: List[str]) -> int:\n",
    "        words.sort(key=len)\n",
    "\n",
    "        f = {}\n",
    "        for s in words:\n",
    "            res = 0\n",
    "            for i in range(len(s)):\n",
    "                res = max(res, f.get(s[:i] + s[i+1:], 0))\n",
    "            f[s] = res + 1\n",
    "        return max(f.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestStrChain(self, words: List[str]) -> int:\n",
    "        \n",
    "        wordDict={}\n",
    "        ld=defaultdict(list)\n",
    "        for word in words:            \n",
    "            ld[len(word)].append(word)\n",
    "            wordDict[word]=1\n",
    "        lk=list(ld.keys())\n",
    "        lk.sort(reverse=True)\n",
    "\n",
    "        for l in lk:\n",
    "            if l-1 in ld:\n",
    "                for word in ld[l]:                   \n",
    "                    for r in range(l):\n",
    "                        rword=word[:r]+word[r+1:]\n",
    "                        if rword in wordDict:\n",
    "                            wordDict[rword]=max(wordDict[rword],wordDict[word]+1)\n",
    "                       \n",
    "        return max(wordDict.values())\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestStrChain(self, words: List[str]) -> int:\n",
    "        # dp[i]表示以words[i]结尾的最长单词链\n",
    "        dp = []\n",
    "        ans = 1\n",
    "        words = sorted(words, key=lambda x:len(x))\n",
    "        for word in words:\n",
    "            temp = [word]\n",
    "            for sub in dp:\n",
    "                if len(sub[-1])+1 == len(word) and self.is_chain(sub[-1], word) and len(sub)+1 > len(temp):\n",
    "                    temp = sub + [word]\n",
    "                    ans = max(ans, len(temp))\n",
    "            dp.append(temp)\n",
    "        print(dp)\n",
    "        return ans\n",
    "                    \n",
    "    def is_chain(self, short_word, long_word):\n",
    "        need_to_find = 0\n",
    "        short_length = len(short_word)\n",
    "        long_length = len(long_word)\n",
    "        index = 0\n",
    "        while need_to_find<short_length and index<long_length:\n",
    "            if short_word[need_to_find] == long_word[index]:\n",
    "                need_to_find += 1\n",
    "            index += 1\n",
    "        return need_to_find == short_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestStrChain(self, words: List[str]) -> int:\n",
    "        def isformer(s1, s2):\n",
    "            if len(s1)-len(s2)!=1: return False\n",
    "            a = 0\n",
    "            for i in range(len(s2)):\n",
    "                if a==0 and s2[i] != s1[i]: a=1\n",
    "                if a==1 and s2[i] != s1[i+1]: return False\n",
    "            return True\n",
    "        @cache\n",
    "        def longestChain(s):\n",
    "            if s not in d: return 1\n",
    "            return 1+max(longestChain(i) for i in d[s])\n",
    "        d = collections.defaultdict(list)\n",
    "        for i in words:\n",
    "            for j in words:\n",
    "                if isformer(i, j): d[j].append(i)\n",
    "        return max(longestChain(i) for i in d) if d else 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestStrChain(self, words: List[str]) -> int:\n",
    "        n = len(words)\n",
    "        words.sort(key=lambda w:len(w)) #按长度排序\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                # if i -> j\n",
    "                w, v = words[i], words[j]\n",
    "                if len(w) + 1 == len(v): \n",
    "                    # 检查移除v的哪个字母能让他们相等\n",
    "                    for k in range(0,len(v)):\n",
    "                        # 移除k [0:k] + [k+1:n]\n",
    "                        u = v[:k] + v[k+1:]\n",
    "                        if u == w:\n",
    "                            graph[i].append(j)\n",
    "        \n",
    "        # print(graph)\n",
    "        # dfs找图上最长path, 一定是 DAG\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            res = 0\n",
    "            for j in graph[i]:\n",
    "                res = max(res, dfs(j))\n",
    "            return res + 1 \n",
    "        return max(dfs(i) for i in range(n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestStrChain(self, words: List[str]) -> int:\n",
    "\n",
    "\n",
    "        # 子序列 选或不选\n",
    "        # n = len(words)\n",
    "\n",
    "        # 直接思路是一个个字符串比对 手动建图\n",
    "        # 但直接利用hash (set) 能更快实现，而且能对原始输入去重\n",
    "        # dfs 不再以i为单位，图的节点是字符串，直接以string为图节点入口\n",
    "\n",
    "        # ws = set(words)\n",
    "        # @cache\n",
    "        # def dfs(v): # v = word[i]\n",
    "        #     res = 0\n",
    "        #     for k in range(len(v)):\n",
    "        #         u = v[:k] + v[k+1:]\n",
    "        #         if u in ws:\n",
    "        #             res = max(res, dfs(u)) \n",
    "        #     return res + 1 \n",
    "        # return max(dfs(v) for v in ws)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # 更新建图 然后找最长路径\n",
    "        n = len(words)\n",
    "        wm = {words[i] : i for i in range(n)}\n",
    "        graph = [[] for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "                # if i -> j\n",
    "            w = words[i]\n",
    "            for k in range(len(w)):\n",
    "                v = w[:k] + w[k+1:]\n",
    "                if v in wm:\n",
    "                    graph[i].append(wm[v])\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            res = 0\n",
    "            for j in graph[i]:\n",
    "                res = max(res, dfs(j)) \n",
    "            #先找到子节点的最长路径，然后加上本身的1\n",
    "            return res + 1 \n",
    "        return max(dfs(i) for i in range(n))\n",
    "\n",
    "        #v1\n",
    "        # # 建图 然后找最长路径\n",
    "        # n = len(words)\n",
    "        # words.sort(key=lambda w:len(w)) #按长度排序\n",
    "        # graph = [[] for _ in range(n)]\n",
    "        # for i in range(n):\n",
    "        #     for j in range(i+1, n):\n",
    "        #         # if i -> j\n",
    "        #         w, v = words[i], words[j]\n",
    "        #         if len(w) + 1 == len(v): \n",
    "        #             # 检查移除v的哪个字母能让他们相等\n",
    "        #             for k in range(0,len(v)):\n",
    "        #                 # 移除k [0:k] + [k+1:n]\n",
    "        #                 u = v[:k] + v[k+1:]\n",
    "        #                 if u == w:\n",
    "        #                     graph[i].append(j)\n",
    "        \n",
    "        # # print(graph)\n",
    "        # # dfs找图上最长path, 一定是 DAG\n",
    "        # @cache\n",
    "        # def dfs(i):\n",
    "        #     res = 0\n",
    "        #     for j in graph[i]:\n",
    "        #         res = max(res, dfs(j)) \n",
    "        #     #先找到子节点的最长路径，然后加上本身的1\n",
    "        #     return res + 1 \n",
    "        # return max(dfs(i) for i in range(n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestStrChain(self, words: List[str]) -> int:\n",
    "        words.sort(key=len)\n",
    "        d = defaultdict(int)\n",
    "        ans = 0\n",
    "        for s in words:\n",
    "            x = 1\n",
    "            for i in range(len(s)):\n",
    "                t = s[:i] + s[i + 1:]\n",
    "                x = max(x, d[t] + 1)\n",
    "            d[s] = x\n",
    "            ans = max(ans, x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestStrChain(self, words: List[str]) -> int:\n",
    "        g = defaultdict(int)\n",
    "        ws = sorted(words, key=len)\n",
    "        res = 0\n",
    "        for w in ws:\n",
    "            x = 1\n",
    "            for i in range(len(w)):\n",
    "                t = w[:i] + w[i + 1:]\n",
    "                x = max(x, g[t] + 1)\n",
    "            g[w] = x\n",
    "            res = max(res, x)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def longestStrChain(self, words: List[str]) -> int:\n",
    "\n",
    "        words.sort(key=len)\n",
    "        from collections import defaultdict\n",
    "        d = defaultdict(int)\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        for s in words:\n",
    "\n",
    "            x = 1\n",
    "\n",
    "            for i in range(len(s)):\n",
    "\n",
    "                t = s[:i] + s[i + 1:]\n",
    "\n",
    "                x = max(x, d[t] + 1)\n",
    "\n",
    "            d[s] = x\n",
    "\n",
    "            ans = max(ans, x)\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestStrChain(self, words: List[str]) -> int:\n",
    "        def isformer(s1, s2):\n",
    "            if len(s1)-len(s2)!=1: return False\n",
    "            a = 0\n",
    "            for i in range(len(s2)):\n",
    "                if a==0 and s2[i] != s1[i]: a=1\n",
    "                if a==1 and s2[i] != s1[i+1]: return False\n",
    "            return True\n",
    "        @cache\n",
    "        def longestChain(s):\n",
    "            l = [i for i in words if isformer(i, s)]\n",
    "            if not l: return 1\n",
    "            return 1+max(longestChain(i) for i in l)\n",
    "        return max(longestChain(i) for i in words)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestStrChain(self, words: List[str]) -> int:\n",
    "        @functools.cache\n",
    "        def dfs(cur: str) -> int:\n",
    "            ret = 0\n",
    "            for i in range(len(cur)):\n",
    "                tmp = cur[0: i] + cur[i + 1:]\n",
    "                if tmp in store[len(cur) - 1]:\n",
    "                    ret = max(ret, dfs(tmp) + 1)\n",
    "            nonlocal ans\n",
    "            ans = max(ans, ret + 1)\n",
    "            return ret\n",
    "\n",
    "        ans = 0\n",
    "        store = collections.defaultdict(set)\n",
    "        for word in words:\n",
    "            store[len(word)].add(word)\n",
    "        for word in words:\n",
    "            dfs(word)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestStrChain(self, words: List[str]) -> int:\n",
    "        @cache\n",
    "        def dfs(s):\n",
    "            res = 0\n",
    "            for i in range(len(s)):\n",
    "                t = s[:i]+s[i+1:]\n",
    "                if t in words:\n",
    "                    res = max(res, dfs(t))\n",
    "            return res+1\n",
    "    \n",
    "        return max(dfs(s) for s in words)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestStrChain(self, words: List[str]) -> int:\n",
    "        # insert additional letter at each place for each letter and check\n",
    "        \n",
    "        memo = {}\n",
    "        def dfs(s):\n",
    "            if s in memo:\n",
    "                return memo[s]\n",
    "            res = 1\n",
    "\n",
    "            for i in range(0 , len(s)):\n",
    "                newstr = s[:i] + s[i+1:]\n",
    "                print(newstr)\n",
    "                if newstr in words:\n",
    "                    res = max(res , 1 + dfs(newstr))\n",
    "                \n",
    "            memo[s] = res\n",
    "            return res\n",
    "        \n",
    "        ret = 0\n",
    "        words.sort(reverse=True)\n",
    "        for word in words:\n",
    "            ret = max(ret , dfs(word))\n",
    "            #print()\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestStrChain(self, words: List[str]) -> int:\n",
    "        ws = set(words)\n",
    "        @cache\n",
    "        def dfs(s):\n",
    "            res = 0\n",
    "            for i in range(len(s)):\n",
    "                t = s[:i] + s[i + 1:]\n",
    "                if t in ws:\n",
    "                    res = max(res, dfs(t))\n",
    "            return res + 1\n",
    "        return max(dfs(s) for s in ws)\n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestStrChain(self, words: List[str]) -> int:\n",
    "        ws = set(words)\n",
    "        @cache\n",
    "        def dfs(s: str) -> int:\n",
    "            res = 0\n",
    "            for i in range(len(s)):\n",
    "                t = s[:i] + s[i+1:]\n",
    "                if t in ws:\n",
    "                    res = max(res, dfs(t))\n",
    "            return res + 1\n",
    "        return max(dfs(s) for s in ws)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
